package com.ohc.leetcode.字符串;

import java.util.HashMap;
import java.util.Map;

/**
 * 2022年5月25日14:13:51
 */
public class 最小覆盖子串76 {
    public static String minWindow(String s, String t) {
        int left = 0;
        int right = 0;
        int len = Integer.MAX_VALUE;
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        int valid = 0;
        int start = 0;
        // 存放需要的子串
        for (int i = 0; i < t.length(); i++) {
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }
        // 移动窗口
        while (right < s.length()) {
            char c = s.charAt(right); // 移入窗口的元素
            right++;

            if (need.containsKey(c)) { // 当前移入窗口的元素是需要的
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (need.get(c) == window.get(c)) {
                    valid++;
                }

            }
            // 当前窗口包含了所需元素的话
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;   // 最小覆盖子串长度
                }

                char c1 = s.charAt(left); // 移除窗口的元素
                left++;
                if (need.containsKey(c1)) {
                    if (need.get(c1) == (window.get(c1))) {
                        valid--;
                    }
                    window.put(c1, window.getOrDefault(c1, 0) - 1);


                }
            }


        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    public static String minWindow2(String s, String t) {
        Map<Character, Integer> needMap = new HashMap<Character, Integer>();
        Map<Character, Integer> windowsMap = new HashMap<Character, Integer>();
        for (char c : t.toCharArray()) {
            needMap.put(c, needMap.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, end = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (needMap.containsKey(c)) { // 如果是需要的子串
                windowsMap.put(c, windowsMap.getOrDefault(c, 0) + 1); // 放入到窗口中
                if (windowsMap.get(c).equals(needMap.get(c))) { // 如果相同的话。。
                    valid++;
                }
            }
            while (valid == needMap.size()) {
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                char d = s.charAt(left);
                left++;
                if (windowsMap.containsKey(d)) {
                    if (windowsMap.get(d).equals(needMap.get(d))) {
                        valid--;
                    }
                    windowsMap.put(d, windowsMap.getOrDefault(d, 0) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    //
//    /**
//     * 暴力初尝试
//     *
//     * @param s
//     * @param t
//     * @return
//     */
//    public static String minWindow3(String s, String t) {
//
//        Map<Character, Integer> need = new HashMap<>();
//        for (int i = 0; i < t.length(); i++) { // 初始化需要的字符串
//            char c = t.charAt(i);
//            need.put(c, need.getOrDefault(c, 0) + 1);
//        }
//        int len = 0;
//        int start = 0;
//        for (int i = 0; i < s.length(); i++) {
//
//            for (int j = 0; j < s.length(); j++) {
//                    if ()
//            }
//
//        }
//        return "";
//    }

    public static String minWindow3(String s, String t) {
        Map<Character, Integer> need = new HashMap<Character, Integer>();
        Map<Character, Integer> window = new HashMap<Character, Integer>();

        int left = 0;
        int right = 0;
        int len = Integer.MAX_VALUE;
        int valid = 0;
        int start = 0;
        for (int i = 0; i < t.length(); i++) { // 保存需要的字符串
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }
        while (right < s.length()) {   // 开始滑动
            char c = s.charAt(right); // 滑入窗口的元素
            right++;

            if (need.containsKey(c)) {  // 如果说当前元素是我们需要的
                window.put(c, window.getOrDefault(c, 0) + 1);              // 就添加到窗口中
                if (need.get(c).equals(window.get(c))) {
                    valid++;
                }
            }
            while (valid == need.size()) {

                if (right - left < len) {
                    start = left;  // 保存 最短字符串
                    len = right - left;   //  保存最小覆盖子串长度
                }
                // 缩小窗口
                char c1 = s.charAt(left);

                left++; // 缩小窗口
                if (window.containsKey(c1)) {
                    if (window.get(c1).equals(need.get(c1))) {  // 如果当前的窗口和需要的数量字符是相同的，就应该快开始扩大窗口了，因为
//                        已经不能覆盖了
                        valid--;
                    }
                    window.put(c1, window.getOrDefault(c1, 0) - 1); // 缩小窗口
                }

            }

        }

            //  AA      B  A C
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    public static void main(String[] args) {
        String s = "DBCDABDC";     /// BANC
        String t = "ABC";
        String s1 = minWindow3(s, t);
        System.out.println("s1 = " + s1);
    }

}
